

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 17655
 * Date: 2025-02-22
 * Time: 12:49
 */
public class test1 {
    /**
     * LeetCode 662 二叉树最大宽度
     */

    public int widthOfBinaryTree(TreeNode root) {
        // 数组模拟队列
        List<Pair<TreeNode,Integer>> q = new ArrayList<>();
        q.add(new Pair<TreeNode,Integer>(root,1));
        int ret = 0;

        while(!q.isEmpty()){
            Pair<TreeNode,Integer> t1 = q.get(0);
            Pair<TreeNode,Integer> t2 = q.get(q.size()-1);
            ret = Math.max(ret,t2.getValue()-t1.getValue()+1);

            // key是这个二叉树的节点值，value是其在数组中的位置
            // 让下一层进队
            List<Pair<TreeNode,Integer>> tmp = new ArrayList<>();
            for(Pair<TreeNode,Integer> t:q){
                TreeNode node = t.getKey();
                int index = t.getValue();
                if(node.left!=null){
                    tmp.add(new Pair<TreeNode,Integer>(node.left,index*2));
                }
                if(node.right!=null){
                    tmp.add(new Pair<TreeNode,Integer>(node.right,index*2+1));
                }
            }
            q = tmp;
        }
        return ret;
    }


    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
     }

     public static class Pair<T, T1>{

         public Pair(T root, T1 i) {

         }

         public T getKey() {
             return null;
         }

         public T1 getValue() {
             return null;

         }
     }
}
